/*
问题 D: 旅游
时间限制: 1 Sec  内存限制: 128 MB
提交: 54  解决: 3
[提交][状态][讨论版]
题目描述
小蓝鲸去了一个奇怪的地方旅游。这里有V个村庄，编号为1到V。有E条路，第i条路将两个村庄ui和vi相连，路的长度是li。

奇怪的是，这里的每个村庄都属于某个联盟。并且属于联盟i的每个村庄都有一条长度为L的路和属于联盟i+1的每个村庄相连。例如：如果村庄1和村庄3属于联盟1，村庄2和村庄4属于联盟2，那么村庄1和村庄2、村庄1和村庄4、村庄3和村庄2以及村庄3和村庄4之间都有长度为L的路相连。

小蓝鲸想知道从村庄1走到村庄V至少需要走多远。

输入
第1行有2个以空格分隔的正整数V和E，1≤V≤5×103 ，1≤E≤105。

第2行是一个正整数L。 

第3行有V个以空格分隔的正整数gi，第i个数gi表示村庄i属于联盟gi。

接下来有E行，每行有3个以空格分隔的正整数ui,vi,li。

1≤li,L≤200, 1≤ui,vi,gi≤V。


输出
一行，一个整数，表示从村庄1走到村庄V至少需要走多远。

如果从村庄1没有路可以走到村庄V，请输出-1。

样例输入
3 3
3
1 3 2
1 2 2
2 3 2
1 3 4
样例输出
3
*/
